package 左哥算法.ch09贪心算法;

import org.junit.Test;

import java.util.*;


public class Ch01 {

    @Test
    public void test(){
        Integer[][] allProject={
                {2,1},
                {1,2},
                {3,3},
                {7,7},
        };
        List<Integer[]> projects = fun(allProject, 3, 3);
        projects.forEach(o->System.out.println(Arrays.toString(o)));
    }

    /**
     * ch01：给你一堆项目，每个项目都有启动资金和它的收益，给你一些初始资金和能最多能做多少次项目，求你的最大获利的情况下能做哪些项目
     *  项目以数组表示，数组的第一位为启动资金，第二位为利润
     * 思路：
     *      1.准备一个小根堆，存放剩余项目，一个大根堆存放已经解锁的项目
     *      2.将所有的项目放入一个小根堆中（主要目的是排序）
     *      3.做项目之前，将所有能做的项目放入大根堆，选择最大的一个做
     *      4.重复3，直到不能做
     */
    public List<Integer[]> fun(Integer[][] projects,int capital,int m){
        List<Integer[]> res=new ArrayList<>();
        PriorityQueue<Integer[]> restQueue=new PriorityQueue<>(Comparator.comparingInt(o -> o[0]));    //剩余的部分
        PriorityQueue<Integer[]> workQueue=new PriorityQueue<>((o1, o2) -> o2[1]-o1[1]);      //解锁的部分
        restQueue.addAll(Arrays.asList(projects));

        for (int i = 0; i < m; i++) {
            while (!restQueue.isEmpty()&&restQueue.peek()[0]<=capital){
                workQueue.add(restQueue.poll());
            }
            if (workQueue.isEmpty()){   //初始资金再无法做任何项目
                return res;
            }
            Integer[] project = workQueue.poll();
            capital+=project[1];
            res.add(project);
        }
        return res;
    }
}
